#include <vector>
#include <queue>
using namespace std;
/*
 * @lc app=leetcode.cn id=55 lang=cpp
 *
 * [55] 跳跃游戏
 */

// @lc code=start
class Solution {
public:
    // bool canJump(vector<int>& nums) {
    //     vector<bool> used(nums.size(), false);
    //     int sz = nums.size();
    //     queue<int> q; q.push(0); used[0] = true;
    //     while (!q.empty()) {
    //         int index = q.front(); q.pop();
    //         if (index == sz - 1) return true;
    //         int num = nums[index];
    //         for (int i = max(0, index - num); i <= min(sz - 1, index + num); i++) {
    //             if (!used[i]) {
    //                 q.push(i); used[i] = true;
    //             }
    //         }

    //     }
    //     return false;
    // }

    bool canJump(vector<int> & nums) {
        int max_jump = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i <= max_jump) max_jump = max(max_jump, i + nums[i]);
            if (max_jump >= nums.size() - 1) return true;
        }
        return false;
    }
};
// @lc code=end

